package com.linchong.sort;

/**
 * @BelongsProject:Algorithm
 * @BelongsPackage:com.linchong.sort
 * @Author:linchong
 * @CreateTime:2019-01-04 22:16
 * @Description:希尔排序
 * 最好时间复杂度O(n),
 * 最差时间复杂度O(n^s)
 * 平均时间复杂度O(nlogn)
 * 空间复杂度：O(1)
 * 不稳定算法
 */
public class ShellSort {
    public static void shellSort(int[] arr,int n){
        int i,j,r;
        int temp;
        for(r = n/2;r>=1;r/=2){
            for(i = r;i<n;i++){
                temp = arr[i];
                j = i-r;
                while(j>=0&&temp<arr[j]){
                    arr[j+r] = arr[j];
                    j -= r;
                }
                arr[j+r] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {3,2,6,5,8,12,4};
        shellSort(arr,arr.length);
        for (int i : arr) {
            System.out.print(" " + i);
        }
    }
}
